//
// Created by Administrator on 2021/8/14.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>> &preferences, vector<vector<int>> &pairs) {
        // 建一个二维矩阵，表示对于i来说，j的亲近程度（越小越亲近）
        vector<vector<int>> rank(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                rank[i][preferences[i][j]] = j;
            }
        }
        // 建立配对数组
        vector<int> match(n);
        for (const auto &pair : pairs) {
            match[pair[0]] = pair[1];
            match[pair[1]] = pair[0];
        }
        int unhappyCount = 0; // 答案
        for (int x = 0; x < n; ++x) {
            int y = match[x]; // 找x的配对
            int index = rank[x][y]; // 对于x而言，y的次序
            for (int i = 0; i < index; ++i) {
                // x 对 u 的亲近程度 大于 x 对 y
                // 找 是否存在一对 x y u v 满足条件
                int u = preferences[x][i];
                int v = match[u];
                if (rank[u][x] < rank[u][v]) {  // u 对 x 的亲近程度 大于 u 对 v
                    ++unhappyCount;
                    break;
                }
            }
        }
        return unhappyCount;
    }
};

int main() {
    vector<vector<int>> preferences{{1, 2, 3},
                                    {3, 2, 0},
                                    {3, 1, 0},
                                    {1, 2, 0}};
    vector<vector<int>> pairs{{0, 1},
                              {2, 3}};
    Solution solution;
    cout << solution.unhappyFriends(4, preferences, pairs) << endl;
    return 0;
}
